//
//  199. 二叉树的右视图.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/25.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution199 {
    // 不就是层序的最后一个节点
    // 二叉树的层序遍历。采用队列
    func rightSideView(_ root: TreeNode?) -> [Int] {
        guard let root = root else {
            return []
        }
        var result: [Int] = []
        var queue: [TreeNode] = [root]
        while !queue.isEmpty {
            var size = queue.count
            while size > 0 {
                let fist = queue.removeFirst()
                if size == 1 {
                    result.append(fist.val)
                }
                if let left = fist.left {
                    queue.append(left)
                }
                if let right = fist.right {
                    queue.append(right)
                }
                size -= 1
            }
        }
        return result
    }
    static func test() {
        let node1 = TreeNode(1)
        let node2 = TreeNode(2)
        let node3 = TreeNode(3)
        let node5 = TreeNode(5)
        let node4 = TreeNode(4)
        node1.left = node2
        node1.right = node3
        node2.right = node5
        node3.right = node4
        
        let solution = Solution199()
        let result = solution.rightSideView(node1)
        print(result)
    }
}
